// 开散列表（用链地址法解决冲突）

const int MaxSize = 100;

// 链表节点

template<typename DataType>
struct Node
{
    DataType data;
    Node<DataType> * next;
};


// 开散列表
class OpenHash
{
private:
    int H(int k);       // 散列函数
    Node<int> *ht[MaxSize];    // 开散列表的存储结构（一个链表）
public:
    OpenHash(/* args */);
    ~OpenHash();
    int Insert(int k); // 插入
    int Delete(int k); // 删除
    Node<int> * Search(int k); // 查找
};

OpenHash::OpenHash(/* args */)
{
    for(int i = 0 ; i<MaxSize; i++)
        ht[i] = nullptr;  // 创建空的闭散列表
}

// 析构函数，将链表的节点循环地delete
OpenHash::~OpenHash()
{
    Node<int> * p = nullptr, *q = nullptr;
    // 对所有链表
    for(int i = 0; i < MaxSize ; i++)
    {
        p  = q = ht[i];
        // 对链表的所有节点
        while (p != nullptr)
        {
            p = p->next;
            delete q;
            q = p;
        }
        
    }
}

// 查找函数
Node<int>* OpenHash::Search(int k)
{
    int j = H(k);   // 计算散列地址
    Node<int> *p = ht[j];   // 工作指针p初始化
    // 对链表循环比较
    while (p != nullptr)
    {
        if(p->data == k)
            return p;
        else
            p = p->next;
    }
    return nullptr; // 查找失败
}